package com.chapter2.sort;

/** 
 * @ClassName: InsertionSort 
 * @Description: 插入排序(正常情况下时间复杂度为O(N2)，但是如果是特殊情况，比如数组是基本有序的，那么才用插入排序的时间复杂度可以达到O(N)，比其他任何数组都快)
 * @author minjun minjun@bw30.com
 * @date 2015-2-14 上午12:40:10 
 *  
 */
public class InsertionSort extends AbstractSort{

	@Override
	public void sort(int[] array) {
		//控制索引从左到右移动，并且保持左边的元素已经排好序
		for(int i=1;i<array.length;i++){
			//拿到第i个元素，往左边插入
			for(int j=i;j>0&&less(array[j],array[j-1]);j--){
				exchange(array, j, j-1);
			}
		}
	}

}
